(1) Field of the Invention
The present invention relates to the field of code-switching in multi-hop wireless networks. More specifically, the present invention pertains to a method and apparatus that uses orthogonal codes as the forwarding labels in multi-hop forwarding.
In order to provide a frame of reference for the present invention, a few basics of networks, and wireless networks, are discussed below.
A mobile ad-hoc network (MANET) has several features, including that it can be set-up anywhere at anytime. There is no need for existing infrastructure. The communication between nodes, can be from node to node, or multi-hop where information starts at a first node, and is sent to a at least one other node en route to a destination node. MANET has many applications, such as implantation in disaster relief situations, where the current infrastructure has been disrupted, or placement in remote areas, where it is expensive to set up infrastructure.
The implantation of MANET requires different routing protocols than those of non-ad-hoc networks. For example, there is no administrator to monitor and control which node is talking to which node and when. Further, MANET implementation has other challenges, such as power consumption. One skilled in the art can appreciate that if nodes are deployed in a disaster relief area or a remote area, power is something that should not be wasted. Thus, it is desirable for each node to expend only the minimum power necessary to accomplish the task of getting information from one node to another.
Network architecture implementation on a particular node comprises several hardware and software layers. These layers are commonly referred to as Open System Interconnection (OSI) layers. These layers describe how applications running upon network-ware devices communicate with each other. The first layer, also referred to as the physical (PHY) layer, defines the physical and electrical characteristics of the network. The network interface cards (NICs) in a computer are an example of hardware which runs at the PHY layer. Essentially, they pass the strings of ones and zeros. The second layer, known as the data link layer, has a sub-layer called the medium access control (MAC) layer and defines the access strategy for sharing the physical medium. Protocols such as point-to-point protocol (PPP) operate here. The third layer, known as the network (NET) layer, provides a means for communicating open systems to establish, maintain, and terminate network connections. The interne protocol (IP) operates at this layer. The fourth layer, known as the transport layer, ensures data reliability and integrity. The transmission control protocol (TCP) operates here. The fifth layer, known as the session layer, provides for two communicating presentation entities to exchange data with each other. The sixth layer, known as the presentation layer, is where application data is either packed or unpacked. The final layer, the seventh layer known as the application layer, is where the end-user and end-application protocols, such as telnet, operate.
The need to conserve energy and reduce latency during network operations has increased with the advent of small wireless devices, such as sensor networks. Further, small wireless devices place demands on system longevity because of their limited power capabilities. Many improvements have come from minimizing the required energy per layer, but the layered OSI driven paradigm of a network (borrowed from the wired networks world) has still remained a dominant factor in the design of a wireless network. Most techniques for power-efficient network operations do not explicitly address power requirements and routing at the hardware layer itself, since the network protocols are easier to implement in software than entirely in hardware at the physical layer.
Therefore, what is needed is a technique which does not require the action of all layers of the OSI model, but instead utilizes only the physical layer when a node is merely relaying information.
Multi-hop wireless networks include mobile ad-hoc networks (MANET) and sensor networks. The networks may be static (no topology changes) or dynamic (with node mobility or environmental changes). Strictly speaking, the term “routing” is often used to mean two different concepts in networking, depending on the context: message-forwarding and network-routing. Message-forwarding refers to the process of receiving a message (packet), consulting a table (the forwarding table), and resending the message towards its destination as determined by that table. Network-routing, on the other hand, refers to the process of building the forwarding table. Message-forwarding is a well-defined process performed locally at each node, whereas network-routing involves a complex distributed decision-making process commonly referred to as the routing algorithm or the routing protocol. Although these two concepts are often mixed together in the discussions of routing in multi-hop wireless networks, these concepts are kept separate in the following description.
First, a look at forwarding in multi-hop wireless networks. There are three fundamental steps involved in forwarding a packet at an intermediate node: 1) receive—the intermediate node receives the packet from the wireless medium; 2) route—the node determines the next-hop for this packet; 3) resend—the node resends the packet back to the wireless medium (towards the next hop). In today's multi-hop wireless network technology, these steps generally span across three OSI layers (physical, data-link, and network). The physical layer usually resides at the radio-frequency (RF) front-end of the NIC, the data-link layer (including MAC) usually resides in the NIC firmware and/or host computer's operating system (OS) kernel (device driver), and the network layer is almost always at the host computer's OS kernel and executed by the host computer's processing unit (CPU). Therefore, each forwarding action must involve RF, NIC, and CPU. For example, IP forwarding in MANET involves the following: when the packet arrives at the intermediate node, it traverses all three layers and is received by the IP input routine in OS kernel. The OS kernel then looks up the next hop address from the kernel IP forwarding table (often called route table). The packet than traverses all three layers again before being sent out for the next hop.
There are several inefficiencies (with respect to energy and latency) for this architecture. First, each packet must traverse the protocol stack merely to know the identity of the next hop neighbor. The processing involved for these operations at both the NIC and the CPU consume significant power. Second, if a node participates in the network, it cannot put itself in sleep mode to conserve energy, because the NIC and CPU must be powered on all times in anticipation of packet forwarding actions. Third, to identify the next hop, the packet must be transmitted in some form of data-link frame (such as MAC header). The framing incurs bandwidth overhead. Finally, since the protocol stack process is usually on a packet-by-packet basis, the node must buffer and receive the entire packet before handing it to the next layer. This can cause additional delay in packet forwarding through any intermediate node.
Therefore, what is needed is to conduct the entire packet forwarding action in one place—the physical layer (e.g., the RF module for a wireless network). This way, only the RF section needs to be powered on to complete a packet forwarding action. The rest of the node, including NIC and CPU, can remain in sleep mode and only respond when there is an incoming packet that is destined for that particular node.
(2) Description of Related Art
MANET routing has been implemented in the art using many different protocols. However, these routing protocols require the processing of the received packets in all three layers (PHY, MAC, and NET) of each intermediate node. What is needed is a routing protocol that proposes to use packet forwarding that is implemented entirely in the physical layer.
Multi-user Code Division Multiple Access (CDMA) has been studied regarding its applicability for multi-hop wireless networks. However, the prior art in this area focuses only on using CDMA as a multiplexing and multi-access tool. What is needed is using CDMA codes to construct a routing/forwarding scheme.